Machine learning models are often susceptible to adversarial perturbations of their inputs. Even small perturbations can cause state-of-the-art classifiers with high standard accuracy to produce an incorrect prediction with high confidence. To better understand this phenomenon, we study adversarially robust learning from the viewpoint of generalization. We show that already in a simple natural data model, the sample complexity of robust learning can be significantly larger than that of standard learning. This gap is information theoretic and holds irrespective of the training algorithm or the model family. We complement our theoretical results with experiments on popular image classification datasets and show that a similar gap exists here as well. We postulate that the difficulty of training robust classifiers stems, at least partially, from this inherently larger sample complexity.

Neural Information Processing Systems http://nips.cc/

Weshowaseparation result: on one hand, if the query radiusλis strictly smaller than the adversary's perturbation budgetρ, then distribution-free robust learning is impossible for a widevarietyofconcept classes; ontheotherhand,thesettingλ=ρallowsusto develop robust ERM algorithms.

Neural Information Processing Systems http://nips.cc/

This paper addresses the question of learning structured distributions from batches when a constant fraction of the batches might be corrupted. This problem has been of considerable recent interest. This paper studies the setting where the underlying distribution has additional structure (namely, piece polynomial density function), in which case more sample efficient algorithms are possible. This paper develops sample and computationally efficient algorithms for such settings. The reviewers were convinced that this paper makes important technical contributions in extending recent work on this problem to the structured setting.